package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可
 * 以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要
 * 用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-length-of-pair-chain
 */
public class 最长数对链_646 {

    public static void main(String[] args) {

        int[][] pairs = new int[][]{{1, 2}, {2, 3}, {3, 4}};
        System.out.println(findLongestChain(pairs));

    }

    /**
     * 动态规划+排序
     * 子问题
     * dp[i] 表示 pairs[0,i] 的最长数对链是多少
     * 从 [i-1,0] 遍历查找第一个符合条件的对链
     *
     * @param pairs
     * @return
     */
    public static int findLongestChain(int[][] pairs) {
        int count = 0;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        // 数组默认是 0，没有加上最开始的那个数对，所以答案需要 +1
        int[] dp = new int[pairs.length];
        for (int i = 1; i < pairs.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = dp[j] + 1;
                    count = Math.max(count, dp[i]);
                    break;
                }
            }
        }
        return count + 1;
    }

}
